#
# @lc app=leetcode.cn id=35 lang=python3
#
# [35] 搜索插入位置
#

# @lc code=start
class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        def bSearch(l,r,n,t):
            if r - l <= 1:
                if nums[l] >=target:
                    return l
                else:
                    return r
            else:
                mid = int((l+r)/2)
                if n[mid] < t:
                    return bSearch(mid,r,n,t)
                else:
                    return bSearch(l,mid,n,t)
        return bSearch(0,len(nums),nums,target)
# @lc code=end

